package main.剑指OfferⅠ;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Day17 {
    public static void main(String[] args) {
        System.out.println("剑指Offer40.最小的K个数");
        System.out.println("剑指Offer41.数据流中的中位数");
    }
}

class Offer40{
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] result=new int[k];
        Arrays.sort(arr);
        for (int i=0;i<k;i++){
            result[i]=arr[i];
        }
        return result;
    }
}

class Offer41{
    PriorityQueue<Integer> queMin;
    PriorityQueue<Integer> queMax;

    public Offer41() {
        queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
        queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
    }

    public void addNum(int num) {
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.offer(queMin.poll());
            }
        } else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }
    }

    public double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.peek();
        }
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}